﻿using System;
using System.Collections.Generic;
using System.IO;

namespace NRank.Common
{
	/// <summary>
	/// Implementation of max heap. Inner items must implement IComparable interface. Item with highest
	/// compare-related value is on the top of the heap.
	/// </summary>
	/// <typeparam name="T">Type of stored items</typeparam>
	public class Heap<T> where T : IComparable
	{
		/// <summary>
		/// Items' stack
		/// </summary>
		private readonly List<T> values = new List<T>(4);

		/// <summary>
		/// Current item count
		/// </summary>
		private int itemCount;

		/// <summary>
		/// Current item count
		/// </summary>
		public int Count { get { return itemCount; } }

		/// <summary>
		/// Inserts item into heap
		/// </summary>
		/// <param name="item">Item to be inserted</param>
		/// <returns>Inserted item</returns>
		public T Add(T item)
		{
			if (values.Count == itemCount)
			{
				++itemCount;
			}

			values.Add(item);
			int index = itemCount - 1;

			BubbleUp(index);

			return item;
		}

		/// <summary>
		/// Bubbles up item at given index
		/// </summary>
		/// <param name="index">Item's index</param>
		private void BubbleUp(int index)
		{
			if (index == 0) return;

			int fatherIndex = ParentIndex(index);

			while (index > 0 && values[fatherIndex].CompareTo(values[index]) < 0)
			{
				Swap(index, fatherIndex);

				index = fatherIndex;
				if (index > 0)
				{
					fatherIndex = ParentIndex(index);
				}
			}
		}

		/// <summary>
		/// Bubbles down item at given index
		/// </summary>
		/// <param name="index"></param>
		private void BubbleDown(int index)
		{
			while (HasSomeSon(index))
			{
				int leftSonIndex = LeftSonIndex(index);
				int rightSonIndex = RightSonIndex(index);

				int greaterSonIndex = leftSonIndex;

				if (rightSonIndex < values.Count)
				{
					if (values[leftSonIndex].CompareTo(values[rightSonIndex]) < 0)
					{
						greaterSonIndex = rightSonIndex;
					}
				}

				bool swapped = false;

				if (values[index].CompareTo(values[greaterSonIndex]) < 0)
				{
					Swap(index, greaterSonIndex);
					index = greaterSonIndex;
					swapped = true;
				}

				if (!swapped) break;
			}
		}

		/// <summary>
		/// Counts index of left son
		/// </summary>
		/// <param name="index">Parent index</param>
		/// <returns>Left son index</returns>
		private static int LeftSonIndex(int index)
		{
			return index * 2 + 1;
		}

		/// <summary>
		/// Counts index of right son
		/// </summary>
		/// <param name="index">Parent index</param>
		/// <returns>Right son index</returns>		
		private static int RightSonIndex(int index)
		{
			return index * 2 + 2;
		}

		/// <summary>
		/// Determines if item at given index has any son
		/// </summary>
		/// <param name="index">Parent index</param>
		/// <returns>True/false if item at given index has any son</returns>
		private bool HasSomeSon(int index)
		{
			return LeftSonIndex(index) < values.Count;
		}

		/// <summary>
		/// Swaps items at given indices
		/// </summary>
		/// <param name="a">First item</param>
		/// <param name="b">Second item</param>
		private void Swap(int a, int b)
		{
			T temp = values[a];
			values[a] = values[b];
			values[b] = temp;
		}

		/// <summary>
		/// Counts parent index
		/// </summary>
		/// <param name="index">Child index</param>
		/// <returns>Parent index of given index</returns>
		private static int ParentIndex(int index)
		{
			if (index <= 0) throw new IndexOutOfRangeException();

			return (index - 1) / 2;
		}

		/// <summary>
		/// Removes top item from heap
		/// </summary>
		/// <returns>Removed item</returns>
		public T RemoveTop()
		{
			if (values.Count == 0) throw new InvalidDataException("Collection is empty");

			int lastIndex = values.Count - 1;

			T item = values[0];

			values[0] = values[lastIndex];
			values.RemoveAt(lastIndex);
			--itemCount;

			BubbleDown(0);

			return item;
		}

		/// <summary>
		/// Gets top item at heap
		/// </summary>
		/// <returns>Top item from heap (without removal, item stays in the heap)</returns>
		public T Peek()
		{
			if (values.Count == 0) throw new InvalidDataException("Collection is empty");

			return values[0];
		}

		/// <summary>
		/// Removes all items
		/// </summary>
		public void Clear()
		{
			values.Clear();
			itemCount = 0;
		}
	}
}